package ArraySorter;

import java.util.Comparator;
public class mergeSort implements MySort
{
    /**
     前置条件：传进一个对象数组,一个实现Comparator接口的类
     后置条件：利用归并排序 对传进来的数组 根据实现的compare方法进行升序排序
     */
    public static<T> void sort(T[] A, Comparator<? super T> cmp)
    {
        T[] tmp = (T[]) new Object[A.length];
        Sorting(A,0,A.length-1,tmp,cmp);
    }

    private static<T> void Sorting(T[] arr,int low,int high,T[] tmp,Comparator<? super T> cmp)
    {
        if(low<high)
        {
            int mid = (low+high)/2;
            Sorting(arr,low,mid,tmp,cmp); //对左边序列进行归并排序
            Sorting(arr,mid+1,high,tmp,cmp);  //对右边序列进行归并排序
            merge(arr,low,mid,high,tmp,cmp);    //合并两个有序序列
        }
    }

    private static<T> void merge(T[] arr,int low,int mid,int high,T[] tmp,Comparator<? super T> cmp)
    {
        int i = 0;
        int j = low,k = mid+1;  //左边序列和右边序列起始索引
        while(j <= mid && k <= high)
        {
            if(cmp.compare(arr[j],arr[k])<0) {tmp[i++] = arr[j++];}
            else  {tmp[i++] = arr[k++];}
        }
        //若左边序列还有剩余，则将其全部拷贝进tmp[]中
        while(j <= mid){tmp[i++] = arr[j++];}
        while(k <= high){tmp[i++] = arr[k++];}
        for(int t=0;t<i;t++) {
            if (tmp[t] != null)
                arr[low + t] =  tmp[t];

            else throw new RuntimeException("传入的两个数据类型不一致！");
        }
    }



    /**
     前置条件：传进一个对象数组
     后置条件：利用归并排序  对传进来的数组 根据实现的compareTo方法进行升序排序
     */
    public static<T> void sort(Comparable<T>[] A)
    {
        //Object[] tmp = new Object[A.length];
        Object[] tmp =  new Object[A.length];
        Sorting(A,0,A.length-1,tmp);
    }
    private static<T> void Sorting(Comparable<T>[] arr,int low,int high,Object[] tmp){
        if(low<high)
        {
            int mid = (low+high)/2;
            Sorting(arr,low,mid,tmp); //对左边序列进行归并排序
            Sorting(arr,mid+1,high,tmp);  //对右边序列进行归并排序
            merge(arr,low,mid,high,tmp);    //合并两个有序序列
        }
    }

    private static<T> void merge(Comparable<T>[] arr,int low,int mid,int high,Object[] tmp){
        int i = 0;
        int j = low,k = mid+1;  //左边序列和右边序列起始索引
        while(j <= mid && k <= high)
        {
            if(arr[j].compareTo((T) arr[k])<0) tmp[i++] = arr[j++];
            else  {tmp[i++] = arr[k++];  }
        }
        //若左边序列还有剩余，则将其全部拷贝进tmp[]中
        while(j <= mid){tmp[i++] = arr[j++];}
        while(k <= high){tmp[i++] = arr[k++];}
        for(int t=0;t<i;t++){  arr[low+t] = (Comparable<T>)tmp[t];  }
    }



}
